package solutions.leetcode.hard;

import solutions.lib.BaseSolution;

import java.util.*;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/frog-jump/">403. 青蛙过河</a>
 */
public class Solution403 extends BaseSolution {

    public boolean canCross(int[] stones) {
        if (stones[1] - stones[0] != 1) {
            return false;
        }
        class Model {
            int pos;
            Set<Integer> steps;

            public Model(int pos) {
                this.pos = pos;
                steps = new HashSet<>();
            }
        }
        List<Model> queue = new LinkedList<>();
        Model first = new Model(1);
        first.steps.add(1);
        queue.add(first);

        int p = 2;
        Set<Integer> remove = new HashSet<>();
        while (p < stones.length) {
            Model now = null;
            for (int i = 0, queueSize = queue.size(); i < queueSize;) {
                remove.clear();
                Model model = queue.get(i);
                int offset = stones[p] - model.pos;
                for (int lastStep : model.steps) {
                    if (offset > lastStep + 1) {
                        remove.add(lastStep);
                    } else if (offset == lastStep + 1) {
                        remove.add(lastStep);
                        if (now == null) {
                            now = new Model(stones[p]);
                        }
                        now.steps.add(offset);
                    } else if (offset >= lastStep - 1){
                        if (now == null) {
                            now = new Model(stones[p]);
                        }
                        now.steps.add(offset);
                    }
                }
                for (int v : remove) {
                    model.steps.remove(v);
                }
                if (model.steps.isEmpty()) {
                    queue.remove(model);
                    queueSize--;
                } else {
                    i++;
                }
            }
            if (now != null && !now.steps.isEmpty()) {
                queue.add(now);
            }
            p++;
        }
        return queue.size() > 0 && queue.get(queue.size() - 1).pos == stones[stones.length - 1];
    }

    public static void main(String[] args) {
        Solution403 solution = new Solution403();
        System.out.println(solution.canCross(new int[] {
                0,1,3,5,6,8,12,17
        }));
    }
}